/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, check whether it is a mirror of itself (ie,
 *              symmetric around its center).
 * 
 *              For example, this binary tree is symmetric:
 * 
 *              	1 
 *                     / \ 
 *                    2   2 
 *                   / \ / \ 
 *                  3  4 4  3 
 *              
 *              But the following is not: 
 *              	1 
 *                     / \ 
 *                    2   2 
 *                     \   \ 
 *                      3   3 
 *              
 *              Note: Bonus points if you could solve it both recursively
 *              and iteratively.
 */
public class SymmetricTree {

    private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
	    val = x;
	}
    }

    public boolean isSymmetric(TreeNode root) {
        if (null == root)
            return true;
        
        return isSymmetric(root.left, root.right);
    }
    
    private boolean isSymmetric(TreeNode p, TreeNode q) {
        if (null == p && null == q)
            return true;
        else if (null == p || null == q)
            return false;
        
        if (p.val == q.val)
            return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
        else
            return false;
    }

    @Test
    public void test() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(2);
	TreeNode n4 = new TreeNode(3);
	TreeNode n5 = new TreeNode(3);
	TreeNode n6 = new TreeNode(4);
	TreeNode n7 = new TreeNode(4);
	
	n1.left = n2;
	n1.right = n3;
	n2.right = n4;
	n3.right = n4;
	assert !isSymmetric(n1);
	
	n2.left = n4;
	n2.right = n6;
	n3.left = n7;
	n3.right = n5;
	assert isSymmetric(n1);
    }
}
